'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-18 16:10:40
'''
#
# @lc app=leetcode.cn id=1146 lang=python3
#
# [1146] 快照数组
#

# @lc code=start
class SnapshotArray:

    def __init__(self, length: int):
        self.store = [{0:0} for _ in range(length)]
        self.snap_id=0
        

    def set(self, index: int, val: int) -> None:
        self.store[index][self.snap_id]=val
        

    def snap(self) -> int:
        self.snap_id +=1
        return self.snap_id-1
        

    def get(self, index: int, snap_id: int) -> int:
        tmp = self.store[index]
        if snap_id in tmp:
            return tmp[snap_id]
        k=list(tmp.keys())
        import bisect
        ind_k=bisect.bisect_left(k, snap_id)
        return tmp[k[ind_k-1]]
        


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)
# @lc code=end

